package baseclass.i_GreedyStrategy;

import java.util.PriorityQueue;

/**
 一块金条切成两半,是需要花费和长度数值一样的铜板的。
 比如长度为20的金条， 不管切成长度多大的两半，都要花费20个铜板。
 一群人想整分整块金条，怎么分最省铜板？
 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60.
 金条要分成10,20,30三个部分。如果，先把长度60的金条分成10和50，
 花费60再把长度50的金条分成20和30，花费50一共花费110铜板。
 但是如果，先把长度60的金条分成30和30，花费60再把长度30
 金条分成10和20，花费30 一共花费90铜板。
 输入一个数组， 返回分割的最小代价。

 分析：  这类问题利用h霍夫曼编码的思想解决。比如数组是{1,4,5,2,6},把数组放入小根堆。
        先找出最小的两个最为叶子1,2他俩的和作为父3
        小根堆变成{3,4,5,6}，再把3和4拿出来形成父7，小根堆{5,6,7},再拿出5,6形成父11,
        小根堆{11,7}最后11和7形成父18。

    利用贪心思想，每次只找小根堆中最小的两个元素。该元素可能是之前已经被若干元素合成的代价。
 */
public class LessMoney {

    public static int lessMoney(int[] arr) {
        //优先级队列，实现堆结构
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        //把目标需求放入小根堆
        for (int i = 0; i < arr.length; i++) {
            pQ.add(arr[i]);
        }
        int sum = 0;
        int cur = 0;
        while (pQ.size() > 1) {
            //从中拿出两个最小的元素
            cur = pQ.poll() + pQ.poll();
            //每次都要累计已经花费的代价,其实是所有非叶子节点的和
            sum += cur;
            //把和代价放入堆
            pQ.add(cur);
        }
        return sum;
    }


    public static void main(String[] args) {
        // 如果从霍夫曼编码树来看，所有的叶子节点就是需求的最终结果
        // 所有的非叶子节点的和(每次小根堆中最小两个点的和累计)就是需要的最小代价
        // 形成霍夫曼树反过来就是切割的过程
        // 长度为30的铜板，分成6,7,8,9
        int[] arr = { 6, 7, 8, 9 };
        System.out.println(lessMoney(arr));
        // 长度为18的铜板，分成1,2,4,5,6,
        int[] arr1 = { 1,2,4,5,6 };
        System.out.println(lessMoney(arr1));
        // 长度为60的铜板，分成10,20,30
        int[] arr2 = { 10,20,30 };
        System.out.println(lessMoney(arr2));




    }
}
